package com.basic;

import java.util.ArrayList;
import java.util.List;

/**
 * HuiSu..https://blog.csdn.net/u012156116/article/details/79673523
 *
 * @author Lizhong
 * @date 2019/9/29
 */
public class HuiSu {


    public static void main(String[] args) {
        // ArrayList<ArrayList<Integer>> combine = combine(new int[]{1, 2, 3});
        // System.out.println(combine.toString());
        List<List<String>> lists = splitString("123");
        System.out.println(lists);
        char[] data = "abcesfcsadee".toCharArray();
        char[] line = "absscde".toCharArray();
        boolean b = hasPath(data, 4, 3, line);
        System.out.println(b);
    }

    /**
     * nums
     * @param nums
     * @return
     */
    public static ArrayList<ArrayList<Integer>> combine(int[] nums) {
        ArrayList<ArrayList<Integer>> result = new ArrayList<>();
        ArrayList<Integer> list = new ArrayList<>();
        backtracing(result, list, 0, nums);
        return result;
    }

    public static void backtracing(ArrayList<ArrayList<Integer>> result, ArrayList<Integer> list, int start, int[] nums) {
        result.add(new ArrayList<>(list));
        for (int i = start; i < nums.length; i++) {
            list.add(nums[i]);
            backtracing(result, list, i + 1, nums);
            list.remove(list.size() - 1);
        }
    }

    /**
     * 切割数字"123" -> [1,2,3],[12,3],[1,23]
     */
    public static List<List<String>> result = new ArrayList<>();    // 首先新建一个 result

    public static List<List<String>> splitString(String s) {
        List<String> list = new ArrayList<>();
        backtraceing(s, 0, list);                                    // 回溯函数
        return result;
    }

    public static void backtraceing(String s, int start, List<String> list) { // start标注每次的起始位置
        if (start > s.length()) {
            return;
        } else if (start == s.length()) {
            result.add(new ArrayList<>(list));
        } else {
            for (int i = start; i < start + 2 && i < s.length(); i++) {   // i<start+2： 每次划分一个或者两个字符
                String subString = s.substring(start, i + 1);
                list.add(subString);
                backtraceing(s, i + 1, list);
                list.remove(list.size() - 1);
            }
        }
    }

    /**
     * 查找矩阵中有无整改字符串
     * @param matrix
     * @param rows
     * @param cols
     * @param str
     * @return
     */
    public static boolean hasPath(char[] matrix, int rows, int cols, char[] str)
    {
        if(matrix==null || matrix.length==0 || str==null || str.length==0 || rows<=0 || cols<=0 ||
                rows*cols < str.length){
            return false;
        }
        boolean[] visited = new boolean[rows*cols];
        char[] path = null;
        int start = 0;                       //表示str的起始位置
        for (int i = 0; i < rows; i++) {
            for (int j = 0; j < cols; j++) {
                if(isbacktracing(matrix, i, j, rows, cols, str, visited, start)){   // 从第i，j个位置是否能走通
                    return true;
                }
            }
        }
        return false;

    }
    public  static boolean  isbacktracing(char[] matrix,int i, int j,int rows,int cols,char[] str,boolean[] visited,int start){
        if(start >= str.length){
            return true;
        }else {

            int index = i*cols + j;     //  记录当前访问的节点
            if(i<0 || i>=rows || j<0 || j>=cols || matrix[index] != str[start] || visited[index]){ //判断是否合适或者是否已被访问
                return false;
            }
            visited[index] = true;      //  标记已读
            boolean judge = isbacktracing(matrix,i+1,j,rows,cols,str,visited,start+1)||
                    isbacktracing(matrix,i,j+1,rows,cols,str,visited,start+1)||
                    isbacktracing(matrix,i-1,j,rows,cols,str,visited,start+1)||
                    isbacktracing(matrix,i,j-1,rows,cols,str,visited,start+1);
            if(judge){
                return true;
            }
            visited[index] = false;     // 回退
            return false;               // 搜索不到，返回false
        }
    }
}